package com.hy;

import java.util.*;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:岛屿的最大面积
 * 给你一个大小为 m x n 的二进制矩阵 grid 。
 *
 * 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid
 * 的四个边缘都被 0（代表水）包围着。
 *
 * 岛屿的面积是岛上值为 1 的单元格的数目。
 *
 * 计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。
 * User:Mr.Du
 * Date:2023/8/25
 * Time:19:00
 */
public class MaxAreaOfIsland {

    int[][] dir = {
            {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    int count;
    boolean visited[][];
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int res = 0, tmp = 0;
        for(int i = 0;i < m;i++){
            for(int j  = 0;j < n;j++){
                if(grid[i][j] == 1){
                    res = Math.max(res, dfs(grid, i, j, m, n));
                }
            }
        }
        return res;
    }

    public int dfs(int[][] grid, int i, int j, int m, int n){
        if(i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) return 0;
        grid[i][j] = 0;
        return  dfs(grid, i + 1, j, m, n) +
                dfs(grid, i - 1, j, m, n) +
                dfs(grid, i, j + 1, m, n) +
                dfs(grid, i, j - 1, m, n) + 1;
    }

    public int maxAreaOfIslandWithBfs(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        visited = new boolean[m][n];
        int res = 0, tmp = 0;
        for(int i = 0;i < m;i++){
            for(int j  = 0;j < n;j++){
                if(grid[i][j] == 1 && !visited[i][j]){
                    count = 0;
                    bfs(grid, i, j, m, n);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }

    public void bfs(int[][] grid, int x, int y, int m, int n){
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(x);
        queue.offer(y);
        count++;
        visited[x][y] = true;
        while(!queue.isEmpty()){
            int xx = queue.poll();
            int yy = queue.poll();/**
 * 计算腐烂的橙子数量。
 *
 * @param grid 二维数组表示果园的状态，1 代表新鲜橙子，2 代表腐烂橙子，0 代表空格。
 * @return 如果所有新鲜橙子都腐烂了，返回腐烂过程需要的最小天数；如果无法全部腐烂，则返回 -1。
 */
public int orangesRotting(int[][] grid) {
    // 获取果园的行数和列数
    int m = grid.length, n = grid[0].length, res = 0;
    // 使用队列保存腐烂橙子的位置，以便进行广度优先搜索
    Queue<int[]> queue = new LinkedList<>();

    // 将所有初始状态为腐烂的橙子加入队列
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(grid[i][j] == 2) queue.offer(new int[]{i,j});
        }
    }

    // 广度优先搜索，直到队列为空
    while(!queue.isEmpty()){
        // 当前队列中的橙子数量
        int size = queue.size();
        boolean flag = false; // 标记当前是否有橙子腐烂

        // 遍历当前队列中的所有橙子
        for(int i = 0;i < size;i++){
            int[] d = queue.poll();
            int x = d[0], y = d[1];

            // 尝试从当前腐烂橙子的位置向四个方向传播腐烂
            for(int[] t : xx){
                int xx = x + t[0], yy = t[1] + y;
                // 跳过越界的橙子、已经是腐烂的橙子和空格
                if(xx < 0 || yy < 0 || xx == m || yy == n
                        || grid[xx][yy] == 0 || grid[xx][yy] == 2) continue;

                // 将新鲜橙子变为腐烂橙子，并将其位置加入队列，标记腐烂发生
                grid[xx][yy] = 2;
                flag = true;
                queue.offer(new int[]{xx,yy});
            }
        }
        // 如果本次有橙子腐烂，则结果加一
        if(flag) res++;
    }

    // 检查果园中是否还有新鲜橙子，有则返回 -1，表示无法全部腐烂
    for(int i = 0;i < m;i++){
        for(int j = 0;j < n;j++){
            if(grid[i][j] == 1) return -1;
        }
    }
    return res;
}

            for(int i = 0;i < 4;i++){
                int cxx = xx + dir[i][0];
                int cyy = yy + dir[i][1];
                if(cxx < 0 || cxx >= m || cyy < 0 || cyy >= n) continue;
                if(!visited[cxx][cyy] && grid[cxx][cyy] == 1){
                    queue.offer(cxx);
                    queue.offer(cyy);
                    count++;
                    visited[cxx][cyy] = true;
                }
            }
        }
    }
}
